package com.yinxin.wudasuanfa.dongtaiguihua;

/**
 * @author yinxin
 * @version 1.0
 * @Description:
 * @date 2022/5/511:56
 */
public class positive {
    /**
     * 关于动态规划的见解：动规和递归有很多相似的地方，最显著的特征可以说是阶段性，
     * 二者都有很明显的阶段划分，所以，声明好每一个阶段所需要做的事情以及阶段与阶段之间的转移可以说是重中之重了，
     * 这就涉及几个问题，第一，需要声明好方法（递归）或者数组（动规）具体的意义，
     * 所代表的作用；第二，需要说明好递归处理数据的方式（递归）或者是阶段转移方程（动规）。
     * 第三，跳出方法的条件（递归）或者是数组边界条件（动规）。处理好这三个方面，基本上就没有问题，剩下的就是一些边边角角的问题。
     */
    public static void main(String[] args) {
        int[][] arr = new int[][]{{13}, {11, 8}, {12, 7, 26}, {6, 14, 15, 8}, {12, 7, 13, 24, 11}};
        System.out.println(arr.length);
        System.out.println(positive(arr));
    }
    /**
     * 顺推 dp
     * 含义：f[x][y] 从0,0到x,y最大值
     * 方程：f[x][y] = max{f[x-1][y],f[x-1][y-1]} + a[x][y]
     * 边界：f[0][0] = a[0][0]
     */
    public static int positive(int[][] a) {
        int[][] f = new int[a.length][a.length];
        // 边界
        f[0][0] = a[0][0];

        // 状态转移方程
        int i, j;
        for (i = 1; i < a.length; i++) {
            for (j = 0; j <= i; j++) {
                /*判断是否数组越界,左右两边需单独处理*/
                if (j == 0) {
                    f[i][j] = f[i - 1][j] + a[i][j];
                } else if (j == i) {
                    f[i][j] = f[i - 1][j - 1] + a[i][j];
                } else {
                    int max = Math.max(f[i - 1][j], f[i - 1][j - 1]);
                    f[i][j] = max + a[i][j];
                }
            }
        }

        // 获取最大值
        int temp = 0;
        for (i = 0; i < a.length; i++) {
            if (f[a.length - 1][i] > temp) {
                temp = f[a.length - 1][i];
            }
        }

        return temp;
    }

}
